The present invention relates generally to signal routing techniques for use in optical networks and other types of networks, and more particularly to signal routing techniques for use in networks which are configured in the form of interconnected rings.
Ring networks, such as networks based on synchronous optical network (SONET) rings, are becoming increasingly popular due to their fast restoration capability in the presence of node or link failures. A ring network may be viewed as any network which includes a set of interconnected rings of nodes. Ring network design usually involves the following basic steps: generation of candidate rings, ring selection, demand routing, and ring sizing and costing. For a given network including a set of rings and a set of node-to-node traffic demands, the routing aspect of ring network design generally involves routing each demand across the ring network from its source node to its destination node such that the overall network cost, as a function of the ring capacities required by the routing, is minimized.
There are two types of ring interconnections that are used in ring networks: single ring interworking (SRI) and dual ring interworking (DRI). SRI is a simple interworking technique which uses only one hub node serving as a gateway to move traffic from one ring to another. The hub node has to be a common node shared by the two rings. SRI for a given demand is uniquely defined by two rings and a hub node for that demand. There may be multiple common nodes between two rings, and any one of the common nodes can be used in SRI. Although SRI has the advantage of simplicity, it provides no protection against hub node failure. DRI is designed to overcome this reliability weakness at the price of higher complexity. In DRI, two hub nodes are selected from each ring and paired with the hub nodes on another ring. Cross-ring traffic is moved by sending two copies of a signal from one ring to the other via two hub pairs, with one copy sent on each hub pair. DRI is described in greater detail in, for example, B. Doshi et al, xe2x80x9cDual Ring Interworking: High Penalty Cases and How to Avoid Them,xe2x80x9d Proceedings of ITC Jun. 15, 1997. Unfortunately, conventional routing techniques for DRI are unable to provide optimal routing in many important applications.
Another problem with existing ring network routing techniques is that these techniques often must be implemented in a centralized manner. In a conventional ring network, the complete end-to-end path for a given demand is typically determined by a central provisioning operations system (OS). This type of centralized routing is required because the routing on a given pair of adjacent rings cannot be fully decoupled in a conventional ring network. In other words, a routing decision made with respect to one ring in the network may require changing the routing on another ring. As a result, conventional centralized routing techniques can severely limit the speed and scalability of the ring network. Unfortunately, existing distributed routing techniques are generally unable to provide minimum cost routing of point-to-point demands across a ring network using, for example, information available to local controllers of each individual ring.
The present invention solves the problems associated with conventional centralized routing of traffic demands over a SONET ring network or other type of ring network. In an illustrative embodiment, traffic demands are routed in a ring network by first determining an inter-ring path for a given demand from a source ring to a destination ring in the network, and then independently determining an intra-ring path for the demand on each of the rings in the inter-ring path. In accordance with the invention, intra-ring path provisioning may be fully decoupled from inter-ring path provisioning, such that the demand can be routed substantially more quickly and efficiently than has heretofore been possible using conventional fully-centralized routing. For example, both the routing direction and the interworking nodes for a dual ring interworking (DRI) connection can be determined independently for each of the rings of the inter-ring path. This provides an additional degree of freedom in routing decisions which considerably simplifies the routing process.
The invention may be implemented in the form of a hybrid centralized/distributed network architecture, in which a central operations system or other central controller determines the inter-ring path by applying a shortest path algorithm to a ring graph in which nodes represent rings in the network and links represent ring interconnections in the network. Ring controllers in the rings of the inter-ring path then each independently determine an intra-ring path for their corresponding rings. The ring controllers may also each provide information regarding current ring load to the central controller, such that the information can be used, for example, in determining optimal inter-ring paths for future demands. Once the central controller determines the inter-ring path, it transmits path information to the ring controllers of the rings in the inter-ring path. The information transmitted to a given ring may include, for example, an indication as to whether the given ring is a source ring, a destination ring or a transit ring, identifiers of its neighboring rings in the path, and an identifier and size of the demand.
Although the invention is particularly well suited for use with DRI, the invention can also improve routing performance in single ring interworking (SRI) applications, as well as applications involving combinations of DRI and SRI. Moreover, the invention is applicable to ring networks having arbitrary size, complexity and configuration.